package com.javabasic.algorithm.leetcode;

public class KthSmallestElementInASortedMatrix {

    /**
     * 解法一：利用二分法，由于半有序矩阵的性质，我们可以知道左上和右下的值分别是这个矩阵的最小值和最大值
     * 再利用二分法，拿到在矩阵中排第k小元素
     *
     * 解法二：就是将二维数组转为有序的一维数组[类似归并的解法]，再取一维数组中的排第k小的元素
     * @param matrix
     * @param k
     * @return
     */
    public int kthSmallest(int[][] matrix, int k) {
        int len = matrix[0].length;
        int left = matrix[0][0];
        int right = matrix[len-1][len-1];
        while (left < right) {
            int mid = left + ((right-left)>>1);
            int count = getCount(matrix, mid);
            System.out.println(mid + " " + count);
            if (count < k) {
                left = mid+1;
            } else {
                // hint: 就算count==k,也还是会继续二分，知道分到第一个刚好在矩阵中排第k的元素，这个元素必定就是矩阵中排第k的元素
                right = mid;
            }
        }
        return left;
    }

    /**
     * 获取target,在矩阵中排第几
     * 思路： 由于矩阵是从左到右递增、从上到下递增；
     * 1. 我们可以从左下或者是右上，开始遍历，比较目标值和当前值的大小，决定当前值的走向，并计算小于目标值的个数
     * @param matrix
     * @param target
     * @return
     */
    private int getCount(int[][] matrix, int target) {
        int len = matrix[0].length;
        int maxRow = len-1, minCol = 0;
        int row = 0, col = len-1;
        int result = 0;
        while (row <= maxRow && col >= minCol) {
            if (matrix[row][col] <= target) {
                result += col+1;
                row++;
            } else {
                col--;
            }
        }
        return result;
    }
}
